This invention relates to instruction optimization in computers. More specifically, it relates to compiler optimizations via a method and apparatuses for allowing additional tail call optimizations which can be further refined at link time (i.e. post-compilation).
Compilers translate high-level code, e.g. C++, which is developed by and readable by human beings, into a low-level machine code. This low-level machine code, also commonly known as object code, is a set of instructions that a computer is able to understand and consequently implement. This translation process is known as compilation. Object code is often referred to as executable or execution code when it is run, producing whatever intended functionality of the original programmers.
This compilation process in the past resulted in executable code that was not as efficient as it possibly could be. Over time, various means of optimizing the executable code, based on general observations of the high level code and any other intermediate versions of the code generated during compilation, as well as other time-tested improvements have resulted in greatly improved and more efficient object code, consequently delivering better software performance.
One such long-recognized method of object code optimization is the tail call optimization. A computer program typically includes many invocations of, also known as calls to, other sub-programs, also known as functions or procedures. Each of these calls may in turn call on other different functions. To keep track of where the program should go to after it completes execution of a function, the data structure of a stack is used. This is a last-in-first-out structure, where each stack frame represents one invocation of a function. Specifically in this case, the top of the invocation stack is the frame of the function that is being executed at a given moment. The presence of calls to other procedures typically requires the creation and overhead of a new stack frame for the calling procedure. As the main program runs, the stack will grow as subsequent calls to other procedures are made. When procedures are completed, any stack frames that were created for the lifetime of the procedures are then destroyed.
The case of a procedure containing tail call(s) presents a special opportunity for optimization. A tail call is any call in a procedure, which immediately exits the procedure upon return (i.e. no other executable code is allowed after the call). For those skilled in the art, a procedure containing only tail calls can be optimized to eliminate the need for creating a stack frame by transforming each tail call from doing a formal call to the target code to be that of a simple transfer of control (e.g. unconditional branch/jump operation).